#
# @lc app=leetcode.cn id=493 lang=python3
#
# [493] 翻转对
#
from typing import List


# @lc code=start
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        
        arr1 = nums[:n//2]
        arr2 = nums[n//2:]
        cnt = self.reversePairs(arr1) + self.reversePairs(arr2)
        
        n1 = len(arr1)
        n2 = len(arr2)
        j = 0
        for v1 in arr1:
            while j < n2 and v1 > 2 * arr2[j]:
                j += 1
            cnt += j
            if j == n2:
                break

        p1 = p2 = i = 0
        while i < n:
            if p1 < n1 and (p2 == n2 or arr1[p1] < arr2[p2]):
                nums[i] = arr1[p1]
                p1 += 1
            else:
                nums[i] = arr2[p2]
                p2 += 1
            i += 1
        
        return cnt


# @lc code=end
if __name__ == "__main__":
    s = Solution()

    lst = [1, 3, 2, 3, 1]
    ret = s.reversePairs(lst)
    print(ret, 2)

    lst = [2, 4, 3, 5, 1]
    ret = s.reversePairs(lst)
    print(ret, 3)
